In a denial-of-service (DoS) attack, a malicious client (called the attacker) performs operations designed to partially or completely prevent legitimate clients from communicating with or gaining service from a server (called the victim). DoS attacks are common and cause significant losses. Well-known e-merchants, including Amazon, buy.com, E*Trade, and eBay, are among recent victims. DoS attacks can harm e-merchants in two ways. First, when an e-merchant cannot serve its customers, the e-merchant loses advertising and sales revenues. Second, the e-merchant's clients, advertisers, and investors are frustrated and may therefore seek competing alternatives.
Some DoS attacks can be prevented by proper system administration. These include physical or remote takeover attacks and death-pill attacks. In a physical takeover attack, the attacker gains physical access to components of the Internet Service Provider (ISP) or e-merchant infrastructure (e.g., one or more links, routers, or servers) and compromises their functionality. In a remote takeover attack, the attacker exploits some bug in the infrastructure's software so as to gain privileged access and thus be able to modify the software remotely. In a death-pill attack the attacker sends one or a few packets to an infrastructure component (e.g., router or server) known to contain a bug, such that the packets cause the component to crash. Proper ISP and e-merchant physical security can eliminate physical takeover attacks. Likewise, prompt installation of patches or updates that fix software bugs can prevent future remote takeover or death-pill attacks exploiting those bugs.
On the contrary, congestive DoS attacks cannot be similarly prevented. In a congestive attack, an attacker floods a server with so many packets that the server is unable to respond to requests sent by legitimate clients. Four factors make it difficult to defend against congestive attacks. First, any host connected to the Internet can be used to sustain a congestive attack against any victim also connected to the Internet. By design, the Internet will forward packets from any host to any other host on a best-effort basis, without bounding packet rate or volume. Second, there are many hosts (e.g., in homes and universities) that are connected to the Internet and do not have the benefit of proper system administration. Such hosts often contain bugs or are configured in such a way that attackers can, without authorization, use them as agents, i.e., as the hosts that actually send attack packets to a victim. Agents provide cloaking and leverage to an attacker, i.e., respectively, hide the attacker's identity and multiply the attacker's resources (e.g., bandwidth). Third, attackers can spoof attack packets, i.e., falsify the packets' source addresses. Spoofing is possible because the Internet does not validate source addresses. Spoofing further enhances an attacker's cloaking. Finally, automated tools of increasing sophistication for mounting DoS attacks can be easily downloaded from the Web. Using such tools, even unskilled Web users can mount successful attacks.
The two currently most popular DoS attack techniques, smurf and TCP SYN flooding, are both congestive. In a smurf attack, the attacker sends ICMP echo requests to a network's broadcast address. The attacker spoofs the requests with the victim's address. Therefore, each host in the network sends a reply not to the attacker but to the victim, thus unwittingly becoming an agent of the attack. In a TCP SYN flooding attack, the attacker or its agents send spoofed TCP SYN (i.e., connection request) packets to the victim. Each such bogus request causes the victim to tie up resources that could otherwise be used for requests from legitimate clients.
To prevent smurf attacks, the Internet Engineering Task Force (IETF) has changed the default treatment of directed broadcast packets by routers. Instead of accepting and forwarding directed broadcast packets, routers should now by default drop them. Additionally, to thwart spoofing, the IETF has recommended ingress filtering (see, e.g., P. Ferguson and D. Senie, “Network Ingress Filtering: Defeating Denial of Service Attacks Which Employ IP Source Address Spoofing,” IETF, RFC 2827 (also BCP 0038), May 2000). With ingress filtering, ISP ingress routers should drop a packet that arrives in a port if the packet's source address does not match a prefix associated with the port. Ingress filtering automatically stops attacks that require spoofing. Moreover, if an attack that does not use spoofing occurs, ingress filtering allows the origin of the attack to be determined simply by examining the source addresses of attack packets. Therefore, ingress filtering can speed up recovery from such attacks. Disadvantageously, the IETF's recommendations need to be adopted by many parties (networks unwittingly used in smurf attacks and ISPs) that are thereby burdened with new responsibilities and costs, but receive no compensation for solving what they may consider somebody else's (the e-merchants') problem. Moreover, these recommendations do not deter all possible congestive DoS attacks. Even without spoofing and directed broadcast, attackers can use agents to obtain the cloaking and leverage necessary for successful attacks. Therefore, adoption of these recommendations (particularly ingress filtering) has not been widespread.
IP traceback is a recently proposed alternative to ingress filtering (see, e.g., S. Savage, D. Wetherall, A. Karlin and T. Anderson, “Practical Network Support for IP Traceback,” Proc. SIGCOMM'2000, pp. 295-306, ACM, Stockholm, Sweden, August 2000). Unlike ingress filtering, IP traceback can be effective even if not widely deployed. IP traceback modifies routers so that they probabilistically send traceback information to a packet's destination. Statistical methods allow a victim to use such information to partly reconstruct the attack path (the reconstructed part is that closest to the victim). However, IP traceback has weaknesses that may deleteriously affect the likelihood of its adoption. It appears that attackers can easily defeat IP traceback by making attacks oblique, i.e., by ostensibly targeting neighbors of the victim, rather than the victim itself. Moreover, traceback information sent by routers that are further from the victim than is the closest attacker can be spoofed and therefore needs authentication. The infrastructure necessary for such authentication may add considerable complexity and vulnerabilities of its own. Finally, like ingress filtering, traceback does not stop attackers from using agents, and may increase ISP responsibilities and costs without contributing to ISP revenues.
Victims can often restore their Internet connectivity by simply changing their address in case of an attack. Of course, this solution is not robust against attackers that periodically check the victim's address via the current DNS mapping. A more general solution against congestive DoS attacks consists in combining input logging and rate limiting (see, e.g., “Characterizing and Tracing Packet Floods Using Cisco Routers,” Cisco, available on the Cisco website, cisco.com, at/warp/public/707/22.html). To use these techniques, the victim must initially determine the signature of the attack, i.e., how the attack packets differ from legitimate packets. ISP personnel then install a filter matching the attack's signature in the egress port of the router closest to the victim. The filter generates a log that reveals what ingress port the attack is coming from. Input logging is then iterated for the next upstream router, until the router closest to the origin of the attack is found. A rate-limiting filter matching the attack's signature is then left installed in the ingress port from where the attack is coming.
Input logging and rate limiting have many limitations. First, attackers may perform an oblique attack noted above, i.e. obfuscate the attack by ostensibly targeting a neighbor of the intended victim. Thus, the victim may not have the opportunity to examine attack packets. Second, even if attack packets reach the victim, the signature may be difficult to characterize. For example, an attacker may coordinate agents so that they send endless streams of seemingly legitimate but fruitless requests to the victim, so as to crowd out requests from legitimate clients. Unlike smurf and TCP SYN flooding attacks, such crowding attacks do not cause easily identifiable anomalies at the network or transport layer, and therefore may be difficult to filter in routers. Third, filtering, logging, and rate limiting may not be available or may prohibitively slow down many routers, especially in the network core. Fourth, rate limiting may be unable to distinguish malicious and legitimate packets (e.g., TCP SYN packets) that arrive in the same ingress port. Thus, rate limiting may be ineffective if the attack is evenly distributed among ingress ports. Finally, input logging and rate limiting are often labor-intensive, tedious procedures performed under pressure and usually without adequate compensation to the ISP.
A methodology is needed, therefore, that limits the losses inflicted upon an e-merchant by congestion, whether legitimate or intentionally inflicted upon the e-merchant by an attacker.